package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 */
//给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 
//
// 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "bbbab"  abbbb
//输出：4
//解释：一个可能的最长回文子序列为 "bbbb" 。
//         0 1 2 3 4
//         b b b a b
//         1 2 3 3 4
// 示例 2：
//
//
//输入：s = "cbbd"
/**   0 1 2 3 4 5
 *    b a b b a b       babcdba
 *                      abdcbab
 *    1 1 2 3 4 5
 *
 */

/**
 *              0 1 2 3 4
 *              b b b a b
 *              0 0 0 0 0
 *          b 0 1 1 1 1 1                     1 2 3 3 4
 *          a 0 1 1 1 2 2
 *          b 0 1 2 2 2 3
 *          b 0 1 2 3 3 3
 *          b 0 1 2 3 3 4
 *
 *
 *
 */
/**        0 1 2 3
 *         c b b d
 *      d  0 0 0 1
 *      b  0 1 1 1
 *      b  0 1 2 2
 *      c  1 1 2 2
 *
  */

//输出：2
//解释：一个可能的最长回文子序列为 "bb" 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 886 👎 0

public class 最长回文子序列{
	public static void main(String[] args) {
		Solution solution = new 最长回文子序列().new Solution();
		String s = "bbbab";
//		String s = "cbbd";
		System.out.println(solution.longestPalindromeSubseq(s));

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		// 是不是 将s翻转得到s2,求s与s2的最长公共子序列
//	s与s.reverse()的最长公共子序列即为其最长回文子序列
	public int longestPalindromeSubseq(String s) {
		StringBuffer s2 = new StringBuffer(s).reverse();
//		System.out.println(s);
//		System.out.println(s2);
		int[][] dp = new int[s.length()+1][s.length()+1];
		for (int i = 1; i < s2.length()+1; i++) {
			for (int j = 1; j < s.length()+1; j++) {
				if (s2.charAt(i-1) == s.charAt(j-1)){

						dp[i][j] = dp[i-1][j-1]+1;
				}else{
//					dp[i][j] = dp[i][j-1];
					dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
				}
			}

		}
//		for (int i = 0; i < dp.length; i++) {
//			for (int j = 0; j < dp.length; j++) {
//				System.out.print(dp[i][j]+" ");
//			}
//			System.out.println();
//		}
		return dp[s.length()][s.length()];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
